package com.zyk.java8;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;

/**
 * 数组为1~N => 1~N的长度为N的数组
 * 最小消耗
 *
 * @author zhangsan
 * @date 2021/5/15 10:11
 */
public class MinCostToAppendArr {

    public static int minCost(int[] arr) {
        if (arr == null || arr.length == 0) return 0;
        int N = arr.length;
        int[] count = new int[N + 1];
        int ans = 0;
        for (int num : arr) {   // 计数
            count[num]++;
        }
        Queue<Integer> queue = new ArrayDeque<>();      // 存出现0次的下标, 先进先出.
        for (int i = 1; i <= N; i++) {
            if (count[i] == 0) {
                queue.add(i);
            } else if (count[i] == 1) {
                continue;
            } else {
                // 这个数出现了, 不止1次. 把前边为0 的搞定, 后边为0的搞定
                int c = count[i];
                while (c > 1 && !queue.isEmpty()) {
                    ans += (i - queue.poll());
                    c--;
                }
                // 出来后, 可能我还是 >1. 可能它后边还有0
                if (c > 1) {
                    int nextJump = -1;
                    for (int j = i + 1; c > 1 && j <= N; j++) {
                        if (count[j] == 0) {
                            ans += (j - i);
                            c--;
                            count[j] = 1;
                        } else if (nextJump == -1 && count[j] > 1) {
                            nextJump = j;
                        }
                    }
                    i = nextJump == -1 ? i : nextJump - 1;   // 一会还会 i++
                }
                // 也可能, 它变成1了.
            }
        }
        return ans;
    }

    // 思路二: 排序, 计算
    public static int minCost2(int[] arr) {
        Arrays.sort(arr);
        int N = arr.length;
        int ans = 0;
        for (int i = 1; i <= N; i++) {
            if (arr[i - 1] != i) {
                ans += Math.abs(arr[i - 1] - i);
            }
        }
        return ans;
    }

    // for test
    public static void main(String[] args) {
        int[] arr = {2, 5, 1, 4, 5, 1, 6, 4};
//        int[] arr = {1, 2, 2};
        System.out.println(minCost(arr));
        System.out.println(minCost2(arr));

        /*for (int i = 1; ; i <<= 1) {
            System.out.println("===============size: " + i + "=====================");
            int[] nums = generateRandomArr(i, true);
            int[] nums2 = copyArray(nums);
            long s1 = System.currentTimeMillis();
            int ans1 = minCost(nums);
            long s2 = System.currentTimeMillis();
            int ans2 = minCost2(nums2);  // 会影响原数组
            long s3 = System.currentTimeMillis();
            if (ans1 != ans2) {
                System.out.println("OOPS");
                System.out.println(Arrays.toString(nums));
                System.out.println(ans1 + "\t" + ans2);
                break;
            }
            System.out.println("贪心: " + (s2 - s1));
            System.out.println("排序: " + (s3 - s2));
        }*/
    }

    public static int[] generateRandomArr(int maxLen, boolean fixedSize) {
        maxLen = fixedSize ? maxLen : (int) (Math.random() * maxLen);
        int[] res = new int[maxLen];
        for (int i = 0; i < maxLen; i++) {
            res[i] = (int) (Math.random() * maxLen) + 1;
        }
        return res;
    }

    public static int[] copyArray(int[] arr) {
        int[] ans = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            ans[i] = arr[i];
        }
        return ans;
    }

}
